package newcoder;

import java.util.ArrayList;

/**
 * @Author 肖地洋
 * @Date 2022/5/17 16:25
 */


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
 }

public class NC146 {
    public static TreeNode cyclicShiftTree (TreeNode root, int k) {
        // write code here
        if(root==null) return null;
        ArrayList<ArrayList<TreeNode>> llist = new ArrayList<>();
        ArrayList<TreeNode> list = new ArrayList<>();
        list.add(root);
        llist.add(list);
        while(llist.get(llist.size()-1).size()!=0){
            ArrayList<TreeNode> cur = new ArrayList<>();
            for(TreeNode node:llist.get(llist.size()-1)){
                if(node.val!=-1){
                    cur.add(node.left==null?new TreeNode(-1):node.left);
                    cur.add(node.right==null?new TreeNode(-1):node.right);
                }
            }
            llist.add(cur);
        }
        llist.remove(llist.size()-1);
        llist.remove(llist.size()-1);
        for (ArrayList<TreeNode> a:llist){
            int len = a.size();
            int kk = k%len;
            int i = 0;
            while(i<len/2){ //全部翻转
                TreeNode temp = a.get(i);
                a.set(i,a.get(len-1-i));
                a.set(len-1-i,temp);
                i++;
            }
            i = 0;
            while(i<kk/2){ //前k翻转
                TreeNode temp = a.get(i);
                a.set(i, a.get(kk-1-i));
                a.set(kk-1-i,temp);
                i++;
            }
            i = kk;
            while(i<(len+kk)/2){ //后len-k翻转
                TreeNode temp = a.get(i);
                a.set(i,a.get(len-1-i+kk));
                a.set(len-1-i+kk,temp);
                i++;
            }
        }
        //重建
        int i= 0;
        while (i<llist.size()-1){
            int j= 0;
            ArrayList<TreeNode> nodes = llist.get(i);
            for (TreeNode no :nodes){
                if(no.val!=-1){
                    no.left = llist.get(i+1).get(j).val==-1?null:llist.get(i+1).get(j);
                    j++;
                    no.right = llist.get(i+1).get(j).val==-1?null:llist.get(i+1).get(j);
                    j++;
                }
            }
            i++;
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        cyclicShiftTree(root,1);
    }

}
